﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <string>
using namespace std;

//礼物的最大价值
//https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/
//class Solution {
//public:
//    int maxValue(vector<vector<int>>& grid) {
//        int m = grid.size();
//        int n = grid[0].size();
//        if (m == 1 && n == 1) return grid[0][0];
//        vector<vector<int>> vv(m + 1, vector<int>(n + 1));
//        for (int i = 1; i <= m; ++i)
//        {
//            for (int k = 1; k <= n; ++k)
//            {
//                vv[i][k] = max(vv[i - 1][k], vv[i][k - 1]) + grid[i - 1][k - 1];
//            }
//        }
//        return vv[m][n];
//    }
//};


//下降路径最小和
//https://leetcode.cn/problems/minimum-falling-path-sum/submissions/
//class Solution {
//public:
//    int minFallingPathSum(vector<vector<int>>& matrix) {
//        int n = matrix.size();
//        vector<vector<int>> vv(n + 1, vector<int>(n + 2, INT_MAX)); //m+1行n+2列
//        for (int k = 0; k < n + 2; ++k)
//            vv[0][k] = 0;
//
//        for (int i = 1; i <= n; ++i)
//            for (int k = 1; k <= n; ++k)
//                vv[i][k] = min(min(vv[i - 1][k - 1], vv[i - 1][k]), vv[i - 1][k + 1]) + matrix[i - 1][k - 1];
//
//        int min = INT_MAX;
//        for (int i = 1; i <= n; ++i)
//            if (vv[vv.size() - 1][i] < min) min = vv[vv.size() - 1][i];
//
//        return min;
//    }
//};

//最小路径和
//https://leetcode.cn/problems/minimum-path-sum/submissions/
//class Solution {
//public:
//    int minPathSum(vector<vector<int>>& grid) {
//        int m = grid.size();
//        int n = grid[0].size();
//        vector<vector<int>> vv(m + 1, vector<int>(n + 1, INT_MAX));
//        vv[0][1] = 0; //保证grid[0][0]的值成功初始化到矩阵
//        vv[1][0] = 0; //而其他的值不影响初始化(如果都为0则第一行和第一列都初始化失败，如果都是最大则第一个[0][0]值初始化失败)
//
//        for (int i = 1; i <= m; ++i)
//            for (int k = 1; k <= n; ++k)
//                vv[i][k] = min(vv[i - 1][k], vv[i][k - 1]) + grid[i - 1][k - 1];
//
//        return vv[m][n];
//    }
//};